package Algorithm.handleString;

/**
 * 866.回文素数 https://leetcode.cn/problems/prime-palindrome/
 * 题目简述：求出大于或等于 N 的最小回文素数。
 */
public class PrimePalindrome {

    /**
     * 思路：先找下一个回文数，判断是否为素数，若不是则+1继续找下一个回文数。这显然比先找下一个素数再判断回文效率更高
     */
    public int primePalindrome(int N) {
        while (true) {
            try {
                N = getNextPalindrome(N);
            } catch (Exception e) {
                return -1;
            }
            if (isPrime(N)) return N;
            N++;
        }
    }

    /**
     * 获取下一个>=N的回文数。将左半部分(向上取整)对称复制到右边构造回文串，若构造出的数字大于等于N，则直接返回
     * 否则将左半部分（向上取整）加1，再重新进入循环尝试。从mid向左遍历，9改0，找到第一个非9的字符增1
     */
    private int getNextPalindrome(int N) throws Exception {
        char[] cs = String.valueOf(N).toCharArray();
        int n = cs.length;
        int mid = (n-1) >> 1; //中轴靠左
        while (true) {
            for (int i = 0;i <= mid;i++) { //将左半部分对称复制到右边 构造回文串
                cs[n-i-1] = cs[i];
            }
            int num = Integer.parseInt(String.valueOf(cs)); //throws Exception
            if (num >= N) return num; //若构造出的数字大于等于N，则直接返回
            int j = mid; //否则将左半部分（向上取整）加1，再构造回文串 （例：253）
            while (cs[j] == '9') //此时左半部分不可能是99...，因此可如此操作
                cs[j--] = '0';
            cs[j]++;
        }
    }

    /**
     * 判断一个数N是否为素数，1不是素数。即看能否整除[2, sqrt(N)]中的任意一个数
     */
    private boolean isPrime(int N) {
        if (N <= 1) return false;
        for (int i = 2;i <= Math.sqrt(N);i++) {
            if (N % i == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        int num = (2 << 30) - 1;
        System.out.println(new PrimePalindrome().primePalindrome(num));
    }

}
